package com.itheima.datastructure.priorityqueue;

import com.itheima.datastructure.queue.Queue;

/**
 * 基于<b>无序数组</b>实现-优先级队列 （数字越大优先级越高）
 *
 * @param <E> 队列中元素类型, 必须实现 Priority 接口
 */
@SuppressWarnings("all")
public class PriorityQueue1<E extends Priority> implements Queue<E> {


    Priority[] array;
    int size;

    public PriorityQueue1(int capacity) {
        array = new Priority[capacity];
    }

    @Override //O(1)
    public boolean offer(E value) {
        if (isFull()) return false;
        array[size] = value;
        size++;
        return true;
    }

    @Override  //O(n)
    public E poll() {
        if (isEmpty()) return null;
        int selectMax = selectMax();
        Priority priority = array[selectMax];
        //删除最高优先级元素
        remove(selectMax);
        return (E) priority;
    }

    private void remove(int index) {
        if (index != size - 1) {
            System.arraycopy(array, index + 1, array,
                    index, size - index - 1);
        }
        array[--size] = null; // help GC
    }

    @Override
    public E peek() {
        if (isEmpty()) return null;
        return (E) array[selectMax()];
    }


    /**
     * 获取最高优先级的索引
     *
     * @return maxIndex
     */
    private int selectMax() {
        int maxIndex = 0;
        for (int i = 0; i < size; i++) {
            if (array[i].priority() > array[maxIndex].priority()) {
                maxIndex = i;
            }
        }
        return maxIndex;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }
}
